package com.cet.algorithm.回溯.电话号码的字母组合;

import java.util.*;

/**
 * @program: cet-practice
 * @description: 电话号码的字母组合
 * @author: 陈恩涛
 * @create: 2023-05-28 10:40
 **/
public class LC17 {

    final static Map<String, List<String>> DIGEST_MAP_TO_LETTER = new HashMap<>();

    static {
        DIGEST_MAP_TO_LETTER.put("2", Arrays.asList("a", "b", "c"));
        DIGEST_MAP_TO_LETTER.put("3", Arrays.asList("d", "e", "f"));
        DIGEST_MAP_TO_LETTER.put("4", Arrays.asList("g", "h", "i"));
        DIGEST_MAP_TO_LETTER.put("5", Arrays.asList("j", "k", "l"));
        DIGEST_MAP_TO_LETTER.put("6", Arrays.asList("m", "n", "o"));
        DIGEST_MAP_TO_LETTER.put("7", Arrays.asList("p", "q", "r", "s"));
        DIGEST_MAP_TO_LETTER.put("8", Arrays.asList("t", "u", "v"));
        DIGEST_MAP_TO_LETTER.put("9", Arrays.asList("w", "x", "y", "z"));
    }

    // 结果集
    List<String> result = new LinkedList<>();

    // 收集结果的载体
    StringBuilder s = new StringBuilder();



    /**
     * 九键输入法按两个，有哪些可能得输出排列
     * @param digits 数字按键
     * @return 输出排列
     */
    public List<String> letterCombinations(String digits) {
        // 输入判空
        if (digits != null && digits.length() > 0) {
            backTrace(0, digits);
        }
        return result;
    }

    /**
     * 回溯函数
     * @param idx 遍历的第几个元素
     * @param digits 输入
     */
    public void backTrace(int idx, String digits) {

        // 终止条件
        if (s.length() == digits.length()) {
            result.add(s.toString());
            return;
        }

        // 单层递归逻辑
        List<String> letterList = DIGEST_MAP_TO_LETTER.get(digits.substring(idx, idx + 1));
        for (String letter : letterList) {
            s.append(letter);
            backTrace(idx + 1, digits);
            s.deleteCharAt(s.length() - 1);
        }
    }

    public static void main(String[] args) {
        LC17 lc17 = new LC17();
        System.out.println(lc17.letterCombinations(""));
    }
}
